//给定两个字符串 s 和 t ，判断它们是否是同构的。 
//
// 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。 
//
// 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。 
//
// 
//
// 示例 1: 
//
// 
//输入：s = "egg", t = "add"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "foo", t = "bar"
//输出：false 
//
// 示例 3： 
//
// 
//输入：s = "paper", t = "title"
//输出：true 
//
// 
//
// 提示： 
//
// 
// 
//
// 
// 1 <= s.length <= 5 * 10⁴ 
// t.length == s.length 
// s 和 t 由任意有效的 ASCII 字符组成 
// 
//
// Related Topics 哈希表 字符串 👍 629 👎 0

//同构字符串
package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

class P205IsomorphicStrings {
    public static void main(String[] args) {
        Solution solution = new P205IsomorphicStrings().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isIsomorphic(String s, String t) {
            // return fun1(s, t);
            if (s.length() != t.length()) {
                return false;
            }
            return fun3(s, t) && fun3(t, s);
            // return fun4(s, t);
        }

        private boolean fun4(String s, String t) {
            Map<Character, Character> s2t = new HashMap<>(), t2s = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char a = s.charAt(i), b = t.charAt(i);
                // 对于已有映射 a -> s2t[a]，若和当前字符映射 a -> b 不匹配，
                // 说明有一对多的映射关系，则返回 false ；
                // 对于映射 b -> a 也同理
                if (s2t.containsKey(a) && s2t.get(a) != b ||
                        t2s.containsKey(b) && t2s.get(b) != a)
                    return false;
                s2t.put(a, b);
                t2s.put(b, a);
            }
            return true;
        }

        private boolean fun3(String s, String t) {
            Character[] source = new Character[128];
            for (int i = 0; i < s.length(); i++) {
                char sChar = s.charAt(i);
                char tChar = t.charAt(i);
                int index = sChar - ' ';
                if (source[index] == null) {
                    source[index] = tChar;
                } else {
                    if (source[index] != tChar) {
                        return false;
                    }
                }
            }
            return true;
        }

        private boolean fun2(String s, String t) {
            HashMap<Character, Character> sMap = new HashMap<>();
            for (int i = 0; i < s.toCharArray().length; i++) {
                char schar = s.charAt(i);
                char tChar = t.charAt(i);
                if (sMap.containsKey(schar) && (sMap.get(schar) != tChar)) {
                    return false;
                } else {
                    sMap.put(schar, tChar);
                }
            }
            return true;
        }

        private boolean fun1(String s, String t) {
            if (s.length() != t.length()) {
                return false;
            }
            HashMap<Character, Character> sMap = new HashMap<>();
            HashMap<Character, Character> tMap = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char schar = s.charAt(i);
                char tChar = t.charAt(i);
                // if ((sMap.containsKey(schar) && (sMap.get(schar) != tChar)) ||
                //         (tMap.containsKey(tChar) && (tMap.get(tChar) != schar))) {
                //     return false;
                // } else {
                //     sMap.put(schar, tChar);
                //     tMap.put(tChar, schar);
                // }
                if (sMap.containsKey(schar) && sMap.get(schar) != tChar || !(sMap.containsKey(schar)) && sMap.containsValue(tChar))
                    return false;
                sMap.put(schar, tChar);
            }
            return true;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
